#include "maxheap.h"

struct Maxheap *createMaxheap(struct Data * _array, int _len)
{
	if(_array==NULL&&_len<=0)
	{
		struct Maxheap *_heap=(struct Maxheap *)calloc(sizeof(struct Maxheap),1);
		if(_heap==NULL)
			return NULL;

		if(_len+1>DEFAULT_SIZE)
		{
			_heap->array = (struct Data*)calloc(sizeof(struct Data), _len+1);
			if(_heap->array==NULL)
			{
				free(_heap);
				return NULL;
			}
			_heap->size = _len+1;
			_heap->count = _len;
			
			memcpy((void*)_heap->array, (void*)_array, _len*sizeof(struct Data));
		}
		else
		{
			_heap->array = (struct Data*)calloc(sizeof(struct Data), DEFAULT_SIZE);
			if(_heap->array==NULL)
			{
				free(_heap);
				return NULL;
			}

			_heap->size = DEFAULT_SIZE;
			_heap->count = 0;
		}

		buildHeap(_heap);

		return _heap;
	}
	return NULL;
}

BOOL removeMax(struct Maxheap *_pheap, struct Data *_pdata)
{
	if(_pheap->count<=0)
		return false;
	else
	{
		memcpy((void*)_pdata, (void*)&(_pheap->array[0]), sizeof(struct Data));
		memcpy((void*)&(_pheap->array[0]), (void*)&(_pheap->array[--_pheap->count]), sizeof(struct Data));
		siftdown(_pheap, 0);
		return true;
	}
}

void delMaxheap(struct Maxheap *_pheap)
{
	if(_pheap!=NULL)
	{
		if(_pheap->array!=NULL)
			free(_pheap->array);
		free(_pheap);
	}
}

int leftchild(int pos)
{
	return pos*2+1;
}

int rightchild(int pos)
{
	return pos*2+2;
}

int parent(int pos)
{
	return (pos-1)/2;
}

BOOL insert(struct Maxheap *_pheap, struct Data *data)
{
	if(_pheap->count>=_pheap->size)
	{
		struct Data *delArray = _pheap->array;
		_pheap->size = 2*_pheap->count;
		_pheap->array = (struct Data*)calloc(sizeof(struct Data), _pheap->size);
		if(_pheap->array==NULL)
		{
			_pheap->array = delArray;
			return false;
		}
		memcpy((void*)_pheap->array, (void*)delArray, sizeof(struct Data)*_pheap->size/2);
		free(delArray);
	}

	memcpy((void*)&(_pheap->array[_pheap->count++]), (void*)data, sizeof(struct Data));
	int curr = _pheap->count-1;
	int par = parent(curr);

	while(curr!=0&&_pheap->array[par].num<_pheap->array[curr].num)
	{
		struct Data data;
		memcpy((void*)&data,(void*)&(_pheap->array[par]), sizeof(struct Data));
		memcpy((void*)&(_pheap->array[par]), (void*)&(_pheap->array[curr]), sizeof(struct Data));
		memcpy((void*)&(_pheap->array[curr]), (void*)&data, sizeof(struct Data));

		curr = par;
		par = parent(curr);
	}
	return true;
}

BOOL isLeaf(struct Maxheap *_pheap, int pos)
{
	if((pos>=_pheap->count/2)&&(pos<_pheap->count))
		return true;
	else 
		return false;
}

void buildHeap(struct Maxheap *_pheap)
{
	int i = _pheap->count/2-1;

	for(;i>=0;i--)
		siftdown(_pheap, i);
}

void siftdown(struct Maxheap *_pheap, int pos)
{
	while(isLeaf(_pheap, pos)==false)
	{
		int biggerIndex;
		struct Data data;
		if(rightchild(pos)<_pheap->count)
		{
			if(_pheap->array[pos].num>_pheap->array[leftchild(pos)].num
					&&_pheap->array[pos].num>_pheap->array[rightchild(pos)].num)
				break;
			else
			{
				 biggerIndex = (_pheap->array[leftchild(pos)].num
								>_pheap->array[rightchild(pos)].num)
								?leftchild(pos):rightchild(pos);

				struct Data *swp = &(_pheap->array[biggerIndex]); 
				memcpy((void*)&data, (void*)swp, sizeof(struct Data));
				memcpy((void*)swp, (void*)&(_pheap->array[pos]), sizeof(struct Data));
				memcpy((void*)&(_pheap->array[pos]), (void*)&data, sizeof(struct Data));

				pos = biggerIndex;
			}
		}
		else
		{
			if(_pheap->array[pos].num<_pheap->array[leftchild(pos)].num)
			{
				biggerIndex = leftchild(pos);
				struct Data *swp = &(_pheap->array[biggerIndex]); 
				memcpy((void*)&data, (void*)swp, sizeof(struct Data));
				memcpy((void*)swp, (void*)&(_pheap->array[pos]), sizeof(struct Data));
				memcpy((void*)&(_pheap->array[pos]), (void*)&data, sizeof(struct Data));

				pos = biggerIndex;

			}
			else
				break;
		}
	}
}
























